package Demo1;

//判断链表是否是回文的
//要求时间复杂度为O（n），空间复杂度为O（1）

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        //找到中间节点 把链表翻转 一个从后往前走 一个从前往后走
        //如果二者相遇的时候还都是一样的，就证明链表是回文的
        //如果只有一个节点 那肯定是回文的
        if(head.next == null) {
            return true;
        }

        //翻转链表
        //1、使用快慢指针找到中间位置
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode cur = slow.next;
        //2、翻转
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //翻转完之后开始查找 (考虑奇偶情况 )
        while (head != slow) {
            if(head.val != slow.val) {
                return false;
            }
            if(head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
}
public class t2 {
}
